Search for: All records

Abstract We address a special case of a conjecture of M. Talagrand relating two notions of “threshold” for an increasing family of subsets of a finite setV. The full conjecture implies equivalence of the “Fractional Expectation‐Threshold Conjecture,” due to Talagrand and recently proved by the authors and B. Narayanan, and the (stronger) “Expectation‐Threshold Conjecture” of the second author and G. Kalai. The conjecture under discussion here says there is a fixedLsuch that if, for a given , admits withand(a.k.a.  isweakly p‐small), then admits such a taking values in ( is‐small). Talagrand showed this when is supported on singletons and suggested, as a more challenging test case, proving it when is supported on pairs. The present work provides such a proof. 

Abstract A family of vectors in [ k ] n is said to be intersecting if any two of its elements agree on at least one coordinate. We prove, for fixed k ≥ 3, that the size of any intersecting subfamily of [ k ] n invariant under a transitive group of symmetries is o ( k n ), which is in stark contrast to the case of the Boolean hypercube (where k = 2). Our main contribution addresses limitations of existing technology: while there are now methods, first appearing in work of Ellis and the third author, for using spectral machinery to tackle problems in extremal set theory involving symmetry, this machinery relies crucially on the interplay between up-sets, biased product measures, and threshold behaviour in the Boolean hypercube, features that are notably absent in the problem considered here. To circumvent these barriers, introducing ideas that seem of independent interest, we develop a variant of the sharp threshold machinery that applies at the level of products of posets. 

Abstract A celebrated conjecture of Tuza says that in any (finite) graph, the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge‐disjoint triangles. Resolving a recent question of Bennett, Dudek, and Zerbib, we show that this is true for random graphs; more precisely:urn:x-wiley:rsa:media:rsa21057:rsa21057-math-0001